#include <stdio.h>
#include <stdlib.h>

// 链表节点的定义
struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *reverseBetween(struct ListNode *head, int left, int right) {
    if (left == right) {
        return head;
    }
    struct ListNode *dummy = (struct ListNode *) malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode *prev = dummy;
    // 找到需要反转的起始位置的前一个节点
    for (int i = 1; i < left; i++) {
        prev = prev->next;
    }
    struct ListNode *curr = prev->next;
    // 反转链表节点
    for (int i = left; i < right; i++) {
        struct ListNode *temp = curr->next;
        curr->next = temp->next;
        temp->next = prev->next;
        prev->next = temp;
    }
    struct ListNode *newHead = dummy->next;
    free(dummy);
    return newHead;
}

// 创建链表节点
struct ListNode *createNode(int val) {
    struct ListNode *newNode = (struct ListNode *) malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 打印链表
void printList(struct ListNode *head) {
    struct ListNode *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
}

int main() {
    // 创建示例链表：1->2->3->4->5
    struct ListNode *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);
    int left = 2;
    int right = 4;
    printf("反转前链表：");
    printList(head);
    struct ListNode *newHead = reverseBetween(head, left, right);
    printf("反转后链表：");
    printList(newHead);
    return 0;
}